// 用bitmap做，无法进行子集去重，如[2,2,1]中会得到[2,1]，[2,1]
// 用回溯算法做，可进行同层剪枝

int **res;
int *path, *used;
int pathlen, res_size;

void backtrack(int start, int* nums, int numsSize, int** returnColumnSizes) {
    res[res_size] = malloc(sizeof(int)*pathlen);
    memcpy(res[res_size], path, sizeof(int)*pathlen);
    (*returnColumnSizes)[res_size] = pathlen;
    res_size++;

    for (int i = start; i < numsSize; i++) {
        if (i >= 1 && nums[i] == nums[i-1] && !used[i-1]) continue; //在一个level中，一个数字只能取一次
        path[pathlen++] = nums[i];
        used[i] = 1;
        backtrack(i+1, nums, numsSize, returnColumnSizes);
        pathlen--;
        used[i] = 0;
    }
}
void quick_sort(int arr[], int l, int r) {
    if (l < r) {
        int i = l, j = r;
        int temp = arr[i];
        while (i < j) {
            while (i < j && temp >= arr[j]) j--;
            arr[i] = arr[j];
            while (i < j && temp <= arr[i]) i++;
            arr[j] = arr[i];
        }
        arr[i] = temp;
        quick_sort(arr, l, i-1);
        quick_sort(arr, i+1, r);

    }  
}

int** subsetsWithDup(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    quick_sort(nums, 0, numsSize-1);
    //qsort(nums, numsSize, sizeof(int), cmp);
    int N = 1<<numsSize;    //最多2^numsSize种情况
    res = malloc(sizeof(int *) * N);    
    *returnColumnSizes = malloc(sizeof(int) * N);
    path = malloc(sizeof(int) * numsSize);  //每个解最大numsSize大小
    used = calloc(numsSize, sizeof(int));
    res_size = pathlen = 0;

    backtrack(0, nums, numsSize, returnColumnSizes);
    *returnSize = res_size;
    return res;
}


